package leetcode.cn;

import java.util.Arrays;

/**
 * @version 1.8
 * @Author Djx_hmbb
 * @Date 2023/10/23 9:15
 * @注释:611.有效三角形的个数
 */
public class ValidTriangle {
    /*
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:
输入: nums = [4,2,3,4]
输出: 4*/
    public static int triangleNumber(int[] nums) {
        int len = nums.length;
        int left = 0;
        int c = len-1;
        int right = c-1;
        int count = 0;
        //先对nums进行排序
        Arrays.sort(nums);
        //当c<2时，停止循环判断
        while (c>=2){
            //当left>=right时，停止循环判断
            while (left < right) {
                int sum = nums[left]+nums[right];
                //当a+b>c时，说明a到b之间的数字和b相加都大于c
                //直接相减计算总数即可。
                //当a+b<=c时，就要移动left，判断有没有a+b>c的，但是left必须<right
                if(sum > nums[c]){
                    count += right-left;
                    right--;
                }else if(sum <= nums[c]){
                    left++;
                }
            }
            //当c的所有情况考虑完之后，就要向前移动c，继续判断。
            // 但是c不能<2，因为要保持包括c前面至少有三个数字。
            c--;
            right = c-1;
            left = 0;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {4,2,3,4};
        int i = triangleNumber(nums);
        System.out.println(i);
    }
}
